Re: passwd hashing algorithm

Charlie Watt (watt@sware.com)
Thu, 20 Apr 1995 08:34:28 -0400 (EDT)

-----BEGIN PRIVACY-ENHANCED MESSAGE-----
Proc-Type: 4,MIC-CLEAR
Content-Domain: RFC822
Originator-Certificate:
 MIIBwDCCAWoCEQC43J7oZ50NWTRSVBShvvaXMA0GCSqGSIb3DQEBAgUAMFkxCzAJ
 BgNVBAYTAlVTMRgwFgYDVQQKEw9TZWN1cmVXYXJlIEluYy4xFzAVBgNVBAsTDlNl
 Y3VyZVdhcmUgUENBMRcwFQYDVQQLEw5FbmdpbmVlcmluZyBDQTAeFw05NDA0MDUx
 NzA2NDJaFw05NTA0MDUxNzA2NDJaMHAxCzAJBgNVBAYTAlVTMRgwFgYDVQQKEw9T
 ZWN1cmVXYXJlIEluYy4xFzAVBgNVBAsTDlNlY3VyZVdhcmUgUENBMRcwFQYDVQQL
 Ew5FbmdpbmVlcmluZyBDQTEVMBMGA1UEAxMMQ2hhcmxlcyBXYXR0MFkwCgYEVQgB
 AQICAgQDSwAwSAJBDNmUqe2+nqg6iuUWzxaXegxki426RzmVNO6VHHYCV4nbo/WL
 X9a7Jn/2nWqZUK/l+RXqCHU/21Ur9jFIt4GNHhcCAwEAATANBgkqhkiG9w0BAQIF
 AANBAEY6kP5jHqK9B9PhZCCJ9mckYuKMufWr7l61LulXGwUTqFzjFC0MOYwXo5s+
 8lqrLQ7YpTzyE74pKR1cl5TAUU4=
Issuer-Certificate:
 MIIBkDCCAToCEQCFP7oDPZq0SSDfetbu5nSkMA0GCSqGSIb3DQEBAgUAMEAxCzAJ
 BgNVBAYTAlVTMRgwFgYDVQQKEw9TZWN1cmVXYXJlIEluYy4xFzAVBgNVBAsTDlNl
 Y3VyZVdhcmUgUENBMB4XDTk0MDQwNTE3MDQyM1oXDTk1MDQwNTE3MDQyM1owWTEL
 MAkGA1UEBhMCVVMxGDAWBgNVBAoTD1NlY3VyZVdhcmUgSW5jLjEXMBUGA1UECxMO
 U2VjdXJlV2FyZSBQQ0ExFzAVBgNVBAsTDkVuZ2luZWVyaW5nIENBMFkwCgYEVQgB
 AQICAgADSwAwSAJBAL4Od/KxhOB6HyUbBJC2X6Ic2P0XEcGnddzJ1QEHjSFyx5qz
 n098ScMWDEJSiwrsVmQFbNvN01hkke7ZE21aG5sCAwEAATANBgkqhkiG9w0BAQIF
 AANBAIBzwWRF5SkoGAdcliVyog2caFtsPrq7lyBIp562B+ckFNderoDTc+JW+i4f
 MhnY9Q9I2KrlZV4GqcpZ+GjAeNk=
MIC-Info: RSA-MD5,RSA,
 C/dXGbJVyUHsW3RKgjgdP6LjX9xElpBce+VaEeYXe7YAAR6eZLUg/yfbiKPXH7h1
 6jmTENkn72Go6RuxH9XTlco=

X-Sensitivity-Label: 1,CMW+3.0/SCO_2.1/sware.com,UNCLASSIFIED
X-Information-Label: 1,CMW+3.0/SCO_2.1/sware.com,UNCLASSIFIED

> 
> > SecureWare has modified
> > the behavior of password hashing not to increase the strength of the
> > underlying crypt(), but to increase the size of the possible password space
> > and the resulting hash value.  The algorithm breaks a password into crypt-
> > sized blocks, running crypt() across each block.  The salt for each block is
> > derived from the ciphertext of the previous block to provide linkage between
> > the individual blocks.  The resulting hash is the concatenation of the 
> > various ciphertext blocks, prefixed with the initial salt.
> 
> This sounds like it could have a real weakness.  Passwords that are longer
> than 8 characters tend to be only a little longer - most of them will be
> 9-12 characters.  Few passwords will be 16 characters.  With this algorithm
> it's easy to crack the last block, using the salt derived from the
> 2nd-to-last ciphertext by trying all 1-4 character strings.  Given the last
> block of cleartext you can make some good guesses about the earlier blocks
> (If the last block is cracked and turns out to be 'h', you can try
> 'elizabeth', if it's 'ia' you can try 'california' etc.).  My guess is a
> 9-12 character password would be weaker than an 8-character password under
> this scheme unless you were careful to keep the first 8 characters totally
> independent of the rest, putting a semantic boundary in the password.
> 
> How about a variation where each block of cleartext was xor'ed with all of
> the previous blocks of cleartext before crypting?

This is an interesting point.  In practice there shouldn't be a hole, for
those sites that care about password management do not allow users to 
choose their own passwords.  

However, the end effect is not as strong as it could be.  Making an
attacker crack both an 8 byte random password and a second 1 - 8 byte random 
password is much better than current practice, but it is not nearly as 
difficult as cracking the corresponding 9 - 16 byte random password.

As you point out, a better cryptographic linkage between blocks would 
force the attacker to search the full password space for a given multiblock
password rather than break it down into separate 8 byte searches.  We will 
incoporate this into our next release.  Thanks for the feedback.  

Charles Watt
SecureWare, Inc.

-----END PRIVACY-ENHANCED MESSAGE-----